package nowcoder.dynamic;

/**
 * 小强现在有
 * 𝑛
 * n个节点,他想请你帮他计算出有多少种不同的二叉树满足节点个数为
 * 𝑛
 * n且树的高度不超过
 * 𝑚
 * m的方案.因为答案很大,所以答案需要模上1e9+7后输出.
 * 树的高度: 定义为所有叶子到根路径上节点个数的最大值.
 * 例如: 当n=3,m=3时,有如下5种方案:
 */
public class BinaryTreeCount {
    public static void main(String[] args) {
        System.out.println(f(3, 3));
    }

    static long mod = 1000000000 + 7;

    public static long f(int n, int m) {
        if (n == 0) {
            return 1;
        }
        if (m == 0) {
            return 0;
        }
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans = (ans + (f(i, m - 1) * f(n - i - 1, m - 1)) % mod) % mod;
        }
        return ans;
    }
}
